perm filename NSF3D[1,BGB] blob
sn#106822 filedate 1974-06-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002
C00004 00003 ABSTRACT:
C00005 00004 I. RELEVANCE TO THE ORIGINAL PROPOSAL.
C00009 00005 II. TECHNICAL DESCRIPTION OF THE WORK.
C00014 00006 III. MILESTONES CHART.
C00017 00007 1. Geometric Modeling System Work.
C00019 00008 3. Mechanical Simulation.
C00022 00009 IV. BUDGET.
C00027 ENDMK
C⊗;
Research Proposal Amendment Submitted to
THE NATIONAL SCIENCE FOUNDATION
for
GEOMETRIC MODELING FOR ASSEMBLY SYSTEMS.
Amending the proposal
EXPLORATORY STUDY OF COMPUTER INTEGRATED ASSEMBLY SYSTEMS.
by
THE STANFORD ARTIFICIAL INTELLIGENCE LABORATORY
MAY 1974
Computer Science Department
School of Humanities and Sciences
STANFORD UNIVERSITY
Stanford, California
ABSTRACT:
This is a request for an additional grant of $19,800 to
support a nine month research program in 3-D geometric modeling for
the visual feedback and manipulation planning portions of the
exploratory study of computer integrated assembly systems.
CONTENTS:
I. RELEVANCE TO THE ORIGINAL PROPOSAL.
II. TECHNICAL DESCRIPTION OF WORK.
III. MILESTONES CHART.
IV. BUDGET.
I. RELEVANCE TO THE ORIGINAL PROPOSAL.
The main contribution of this amendment to the original
proposal would be to add an existing 3-D polyhedral geometric
modeling system to the already supported work on 2-D vision,
spine-cross section models and semantic models. The main advantage of
a polyhedral model is that surfaces are explicitly represented so
that appearance and collision can be simulated. The work of Mr.
Baumgart, was mentioned in the original proposal; but was to have
been supported on another grant.
We propose to represent and simulate solid objects in a
computer for the sake of visual feedback and manipulation planning.
The project has three phases: acquistion of 3-D models, use of the
models for verification vision and use of the models for collision
avoidance in planning arm trajectories. Models are aquired both by
manually drawing the objects using a 3-D geometric editing program;
or by automatically analysing sequences of television pictures of the
given object. Once acquired, a 3-D model can be used to anticipate
the appearance of an object or a scene of objects by means of an
(existing) hidden line eliminator which generates both video and line
drawing images in a form internally useful to the computer. With good
predicted images available, a quantitative form of vision by
verification (visual feedback) becomes feasible (figure 1, all
figures follow this section). In
particular, the loci of occlusion and shine in a image are
anticipated so that the characteristics of other features can be
measured with less confusion. Finally, routines will be developed
for detecting and avoiding collisions between objects during
simulated manipulations.
The final form of this work will be that of a geometric
modeling system that is accessible through a command langauge which
will be an extension to existing languages such as SAIL (ALGOL) and
LISP. The command language will have routines for object generation,
Euclidean transformations, metrics, I/O, mechanics, image synthesis
and image analysis. All the image processing primitives will be
compatible with the vision language being developed under the
original proposal by T. Binford, R. Taylor and K. Pingle.
II. TECHNICAL DESCRIPTION OF THE WORK.
The proposed work is based on the following ideas and work
already done:
i. Explicit 3-D Object Representation.
The presently implemented explicit object representation is
based on polyhedral models of solid rigid objects. A simple object
is defined by a surface shell of vertices, edges and faces that
satisfy the Euler equation, V - E + F = 2. Such polyhedra are
combined to form compound objects. Curved objects are represented by
approximating them using a polyhedron composed of a sufficient number
of flat polygonal faces.
ii. Object Generation from Physical Description.
A convenient way of making an explicit computer model of an
object is to simulate the process of building the object. That is,
the description of how to build an object is an implicit
representation of the object. For example it is easier to describe
Figure 2 as a dodecahedron with a regular five pointed star shaped
hole cut through it, than it is to draw the figure with a light pen
or to list the loci of its vertices.
iii. Language Extension.
Rather than developing new languages for geometric modeling,
we believe it is best to extend the old languages: ALGOL and LISP.
The elements of language extension include new data types for the
language, general low level primitives for manipulating the new data
types, and a convenient set of higher level operations. The division
of the work into high level operations defined in terms of low level
primitives isolates the data structure manipulating code.
iv. Object Representation from Physical Measurement,
Another way to get an explicit computer model of an object is
to derive it from measurements made on an actual physical object, 2-D
drawing, or picture. We believe that only the lack
of appropriate software is preventing the use of television cameras
as an inexpensive, accurate, and automatic means of entering
graphical data into a computer. (Figure 3)
vi. Mechanical Simulation.
Information, such as the degrees of freedom of motion, is
included in the object description and can be used to get pictures of
objects in different positions.
Mechanical information can also be used to constrain the shape
of a part in its desired place, or to find the space potentially
occupied by a moving part.
vii. Photometric Simulation.
Photometric information such as the location and nature of
light sources and the light scattering properties of the objects'
surfaces can be included in the model and used to compute the actual
appearance of solid opaque objects, (Figure 4). The appearance of shiny
metal is particularly relevant to mechanical assembly since location
and orientation of metallic parts can potentially be found from such
literally glaring, characteric features.
III. MILESTONES CHART.
The goals of the proposed project are summarized in the following list:
Items partially in hand.
1. Representation of solid rigid three-dimensional polyhedra.
2. Language extension of geometric primitives.
3. Language extension of object building operations.
4. Polyhedral object hidden line (and surface) eliminator.
5. Geometric editor.
Items within nine month work.
6. Routines for collision avoidance.
7. Routines for verification vision.
8. Video acquisition of three-dimensional objects.
9. Mechanical simulation and animation.
10. Photometric simulation - shadows and light sources.
In Chart form:
1974 1975
JUL AUG SEP OCT NOV DEC JAN FEB MAR
________________________________________________________________________
| | | |
|←←←←←←← GEOMETRIC MODELING SYSTEMS WORK →→→→→→→→→→→→→→→→→→→→→→→→→→→→→→→|
| | | |
|←←← COLLISION AVOIDANCE →→→→→→→→→→ | |
| | ←←← VERIFICATION VISION →→→→→→→→→→→→→|
|←←← MECHANICAL SIMULATION →→→→→→→→ | |
| | ←←← VIDEO AQUISITION →→→→→→→→→→→→→→→→|
| | | |
| | ←←← PHOTOMETRIC SIMULATION →→→→→→→→→→|
|_______________________|_______________________|_______________________|
JUL AUG SEP OCT NOV DEC JAN FEB MAR
1974 1975
Milestone chart entries detailed:
1. Geometric Modeling System Work.
Futher documentation, debugging and interfacing will be done
to the existing geometric modeling system so that it can be available
as a utility program for the other phases of the assembly systems research
effort.
2. Collision Avoidance.
Simple geometric models fall into two classes: space oriented
models and object oriented models. One essential line of research
involves creating an elegant compound model that facilitates spatial
problem solving while maintaining object coherence. In particular,
planning arm trajectories that avoid collisions requires such a
compound models of object in space. Two lines of work relevant to
collision avoidance will be continued under this grant: first,
spatial sorting of polyhedral objects (which is similar to some of
the hidden line elimination algorithms) and second, trajectory
planning thru empty space (again by employing hidden line elimination
techniques to "see" a clear path to a given goal by looking through
simulated watchdog cameras mounted on the simulated mechanical arm).
3. Mechanical Simulation.
For the sake of mechanical simulation the mass, inertia
tensors, force, torque, friction and gravity characteristic to
polyhedral objects will be added to the modeling routines. Some of
the physical entities, such as the inertia tensors can be done quite
exactly while entities such as friction will merely be caricatured.
4. Verification Vision.
For a first cut, the expected appearance of steps of an
assembly process will be computed by computer graphics techniques and
will be compared with features abstracted from actual television
pictures of the process to verify that all is going as it should.
Simulated images are used rather than stored images of a "training
session" because it is supposed that this first cut is a necessary
preliminary step towards a
verification vision system that can dynamically change its internal
model to discover what went wrong by verifying the
appearance of a particular mishap with its updated internal models.
5. Video Aquisition.
The shape of mechanical parts that are difficult to draw
(such as castings) can be entered into the computer by analysing
sequences of television pictures taken of the object on a turn table.
6. Photometric Simulation.
As already mentioned, work on shine and
shadow simulation will be undertaken to make the relevant
classes of photometric features available to the vision language.
IV. BUDGET.
RESEARCH GRANT PROPOSAL BUDGET
NINE MONTHS BEGINNING 1 JULY 1974
Requested University Total
Budget Category From NSF Contribution Costs
------------------------------------------------------------------------
I. SALARIES & WAGES:
McCarthy, John, $ 0 $ 0 $ 0
Professor,
Principal Investigator
Baumgart, Bruce G., 10,693 107 10,800
Research Associate
9 months FTE
_______ _______ _______
TOTAL SALARIES $10,693 $ 107 $10,800
II. STAFF BENEFITS:
7-1-74 to 8-31-74 @ 17.0% $ 408 $ 0 $ 408
9-1-74 to 3-31-75 @ 18.0% $ 1,512 $ 0 $ 1,512
_______ _______ _______
$ 1,920 $ 0 $ 1,920
III. EXPENDABLE MATERIALS & SERVICES:
A. Telephone Service
B. Office Supplies $ 384 $ 0 $ 384
IV. PUBLICATION COSTS: $ 500 $ 0 $ 500
V. TOTAL DIRECT COSTS:
(ITEMS I THRU IV) $13,497 $ 107 $13,604
VI. INDIRECT COSTS:
On Campus - 47% of NTDC $ 6,303 $ 91 $ 6,394
VII. TOTAL COSTS:
(Items V + VI) $19,800 $ 198 $19,998